A multiprocessing computer system has multiple processes executing on the system. Each process performs a particular task, and the processes, taken as a whole, perform some larger task, called an application. These processes may be executing on a single central computer or they may be running on separate computers which are connected to each other via some type of communication link, i.e. a distributed computer system. As used herein, the term computer includes any device or machine capable of accepting data, applying prescribed processes to the data, and supplying the results of the processes.
In order for the application task to function correctly, the separate processes must coordinate their functions. This coordination is often accomplished through inter-process communication. A system in which inter-process communication is accomplished by processes sending messages to, and receiving messages from, other processes, is called a message passing system.
If a failure occurs in one of the processes, often the entire application must be reinitialized, because each of the processes is dependent on the successful operation of the other processes. In such a case, each of the processes must be rolled back to the beginning of execution. Such reinitialization is very costly, because all the work performed by the application up until the failure is lost. The cost of restarting a computer system in the event of a process failure is reduced by the technique of checkpointing.
Generally, a checkpoint is a snapshot of the state of a process which is saved on non-volatile storage, and which survives process failure. Upon recovery, the checkpoint can be reloaded into volatile memory, and the process can resume execution from the checkpointed state. Checkpointing reduces the amount of lost work in the event of a process failure because the checkpointed processes only need to be rolled back to the last checkpoint. When the processes in a system are rolled back to previous checkpoints, the set of checkpoints to which the processes are rolled back is called the recovery line.
In message passing systems, process rollback is complicated by the need to maintain a consistent state of the system. In a message passing system, the rollback of one process may require the rollbacks of other processes in order to guarantee consistency, of the state of the system as a whole. For example, if the sender of a message m rolls back to a checkpointed state before message m was sent (i.e. unsends m), then the receiver of m must also roll back to a checkpointed state before m was received (i.e. unreceive m). If such rollback procedure is not followed, the states of the two processes together will show that message m has been received but not yet sent, which is inconsistent. The rolling back of multiple processes based on an initial rollback of one process, in order to maintain a consistent system state, is called rollback propagation.
It is noted that in some systems, if a process is rolled back to a checkpointed state before message m is received, it may not be necessary to roll back the sender to a checkpointed state before the message was sent. This is because the receiver may log the message when received. Upon rollback to a checkpointed state prior to receipt of the message, the message remains in the receiver's message log and may be processed upon resumption of execution.
In a system with N processes, a global checkpoint is a set of N checkpoints, one from each process. A consistent global checkpoint is a global checkpoint which results in a consistent system state. It is noted that a system may have more than one consistent global checkpoint.
In multiprocessing systems, resources are often shared among the executing processes. Such resources may include, for example, disk drives, printers, shared memory, and databases. During processing, a process may require exclusive access to a resource, such that another process may not use that resource until the first process is finished with it. Such mutually exclusive sharing of resources may be accomplished by using a resource manager process. Such a resource manager process receives requests for access to a resource from processes, grants exclusive access to the resource to the requesting process if the resource is available, and denies other processes' requests for that resource until the process which was granted access releases the resource.
A problem with mutually exclusive access to resources is the possibility that the computer system will enter a deadlock state. A deadlock state is a state in the computer system in which, because of a resource allocation pattern, the computer system cannot progress past a processing point. For example, consider a computer system with two resources R1 and R2, and two processes P1 and P2, where P1 and P2 both need simultaneous exclusive access to R1 and R2 at some point in order to successfully complete their processing. If P1 gains exclusive access to R1 and R2, then P2 must wait until P1 releases the resources. Such a situation does not present a problem, because it is presumed that P1 will eventually releases the resources, at which time P2 may gain access to the resources. However, consider the situation in which P1 gains access to R1 and P2 gains access to R2. If this occurs, then P1 cannot finish its task until it gains access to R2, and P2 cannot finish its task until it gains access to R1. However, P1 will not release R1 until it gains access to R2, and P2 will not release R2 until it gains access to R1. At this point, the system is in a deadlock state.
When deadlock is detected, one of the processes involved in the deadlock is generally terminated, so that it releases the resource it held, and the resource can be reclaimed by the system. The terminated process is called the victim. The reclaimed resource may then be used by a waiting process. If the waiting process can finish processing using the reclaimed resource, then the system can progress past the deadlock state. Victim selection is generally made on a random basis, or based on a static priority assigned to the processes.
However, the above deadlock recovery mechanism is not sufficient in a multiprocess message passing system because rollback propagation due to message dependencies may force non-terminated processes 16 rollback, resulting in the same deadlock cycle reappearing. For example, in the above example, if P1 is terminated in order to reclaim resource R1 for P2, the termination may require that P2 be rolled back to an execution point before it requested R1. In such a situation, when P1 and P2 resume execution, they may end up in the same deadlock state.